﻿#pragma once
#include<string>
#include<vector>
#include<iostream>
using namespace std;

namespace wzy {
	
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t hashi = 0;
			//BKDR
			for (auto e : s)
			{
				hashi += e;
				hashi *= 131;
			}
			return hashi;
		}

	};

	namespace hash_bucket
	{
		template<class T>
		struct HashNode
		{
			T _data;
			HashNode<T>* _next;
			HashNode(const T& data)
				:_data(data)
				, _next(nullptr)
			{}
		};

		template<class K, class T, class KeyOfT, class Hash>
		class HashTable;


		template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
		struct HTIterator
		{
			typedef HashNode<T> Node;
			typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
			typedef HashTable<K, T, KeyOfT, Hash> HT;

			HTIterator(Node* node,const HT* ht)
				:_node(node)
				,_ht(ht)
			{}

			Ref operator*()
			{
				return _node->_data;
			}

			Ptr operator->()
			{
				return &_node->_data;
			}

			bool operator==(const Self& s)
			{
				return _node == s._node;
			}

			bool operator!=(const Self& s)
			{
				return _node != s._node;
			}

			Self& operator++()
			{
				if (_node->_next)
					_node = _node->_next;
				else
				{
					KeyOfT kot;
					Hash hs;

					size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
					++hashi;
					while (hashi < _ht->_tables.size())
					{
						_node = _ht->_tables[hashi];
						if (_node)
							break;
						else
							++hashi;
					}
				}

				return *this;
			}

			Node* _node;
			const HT* _ht;
		};

		// K 为 T 中key的类型
		// T 可能是键值对，也可能是K
		// KeyOfT: 从T中提取key
		// Hash将key转化为整形，因为哈希函数使用除留余数法
		template<class K, class T, class KeyOfT, class Hash>
		class HashTable
		{
			typedef HashNode<T> Node;

			template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
			friend struct HTIterator;

		public:

			typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
			typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

			Iterator Begin()
			{
				if (_n == 0)
					return End();

				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];

					if (cur)
						return Iterator(cur, this);
				}

			}

			Iterator End()
			{
				return Iterator(nullptr, this);
			}

			ConstIterator Begin() const
			{
				if (_n == 0)
					return End();

				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];

					if (cur)
						return ConstIterator(cur, this);
				}

			}

			ConstIterator End() const
			{
				return ConstIterator(nullptr, this);
			}

			HashTable()
			{
				_tables.resize(10, nullptr);
			}

			// 哈希桶的销毁
			~HashTable()
			{
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						Node* next = cur->_next;
						delete cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
			}

			// 插入值为data的元素，如果data存在则不插入
			pair<Iterator, bool> Insert(const T& data)
			{
				KeyOfT kot;
				Hash hs;

				Iterator it = Find(kot(data));
				//插入的数据已经存在
				if (it != End())
					return { it ,false };

				//负载因子为1时扩容
				if (_n == _tables.size())
				{
					vector<Node*> newHT(_tables.size()*2,nullptr);
					for (size_t i = 0; i < _tables.size(); i++)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;
							//头插到新表里
							size_t hashi = hs(kot(cur->_data)) % newHT.size();
							cur->_next = newHT[hashi];
							newHT[hashi] = cur;

							cur = next;
						}
						_tables[i] = nullptr;
					}

					_tables.swap(newHT);
				}

				size_t hashi = hs(kot(data)) % _tables.size();
				//头插
				Node* newnode = new Node(data);
				newnode->_next = _tables[hashi];
				_tables[hashi] = newnode;
				++_n;
				return { Iterator(newnode,this),true };
			}

			// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
			Iterator Find(const K& key)
			{
				Hash hs;
				size_t hashi = hs(key) % _tables.size();

				//在对应的桶里查找数据
				Node* cur = _tables[hashi];
				KeyOfT kot;
				while (cur)
				{
					if (kot(cur->_data) == key)
						return Iterator(cur,this);

					cur = cur->_next;
				}

				return End();
			}

			// 哈希桶中删除key的元素，删除成功返回true，否则返回false
			bool Erase(const K& key)
			{
				Hash hs;
				KeyOfT kot;
				size_t hashi = hs(key) % _tables.size();
				Node* prev = nullptr;
				Node* cur = _tables[hashi];
				while (cur)
				{
					if (kot(cur->_data) == key)
					{
						//删除结点为头结点
						if (prev == nullptr)
						{
							_tables[hashi] = cur->_next;
						}
						//删除结点为中间结点
						else
						{
							prev->_next = cur->_next;
						}

						delete cur;
						--_n;
						return true;
					}
					else
					{
						prev = cur;
						cur = cur->_next;
					}
				}
				return false;
			}

		private:
			vector<Node*> _tables;  // 指针数组
			size_t _n = 0;			// 表中存储数据个数
		};

	}

	//template<class K>
	//struct Hash
	//{
	//	size_t operator()(const K& key)
	//	{
	//		return key;
	//	}
	//};

	//template<>
	//struct Hash<string>
	//{
	//	size_t operator()(const string& s)
	//	{
	//		size_t hashi = 0;
	//		for (auto e : s)
	//		{
	//			hashi *= 31;
	//			hashi += e;
	//		}
	//		return hashi;
	//	}
	//};

	//template<class K,class T>
	//struct KeyOfT
	//{
	//	const K& operator()(const T& data)
	//	{
	//		return data;
	//	}
	//};

	//template<class K, class T>
	//struct SKeyOfT
	//{
	//	const K& operator()(const T& data)
	//	{
	//		return data.first;
	//	}
	//};


	//void test_int()
	//{
	//	hash_bucket::HashTable<int, const int, KeyOfT<int,int>, Hash<int>> HT;
	//	int a[] = { 12,14,54,17,42,52,18 };
	//	for (auto e : a)
	//	{
	//		HT.Insert(e);
	//	}

	//	cout << HT.Find(42) << endl;
	//	HT.Insert(33);
	//	HT.Insert(13);
	//	HT.Insert(53);
	//	HT.Insert(83);
	//	cout << HT.Find(42) << endl;
	//	HT.Erase(13);
	//	HT.Erase(53);
	//	HT.Erase(12);
	//}

	//void test_string()
	//{
	//	hash_bucket::HashTable<string, pair<string, string>, SKeyOfT<string, pair<string, string>>, Hash<string>> HT;
	//	HT.Insert({ "left","左边" });
	//	HT.Insert({ "right","右边" });
	//	HT.Insert({ "insert","插入" });
	//	HT.Insert({ "delete","删除"});

	//}
}